<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>数据结构深入解析：红黑树与B树对比</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', 'Noto Serif SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f8fafc;
            color: #1e293b;
            line-height: 1.6;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #4f46e5 0%, #7c3aed 100%);
        }
        .code-bg {
            background-color: #1e293b;
            border-left: 4px solid #7c3aed;
        }
        .feature-card {
            transition: transform 0.3s ease, box-shadow 0.3s ease;
        }
        .feature-card:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .visualization-container {
            background: white;
            border-radius: 0.5rem;
            box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1), 0 2px 4px -1px rgba(0, 0, 0, 0.06);
        }
        .drop-cap::first-letter {
            float: left;
            font-size: 4.5rem;
            line-height: 0.65;
            margin: 0.1em 0.1em 0.2em 0;
            color: #4f46e5;
            font-weight: 700;
        }
    </style>
</head>
<body class="antialiased">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-4 sm:px-6 lg:px-8">
        <div class="max-w-4xl mx-auto text-center">
            <h1 class="text-4xl md:text-5xl font-bold mb-6">红黑树 <span class="opacity-80">vs</span> B树</h1>
            <p class="text-xl md:text-2xl font-light max-w-3xl mx-auto opacity-90">
                探索两种关键平衡树结构的设计哲学与应用场景
            </p>
            <div class="mt-10 flex justify-center space-x-4">
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium flex items-center">
                    <i class="fas fa-code-branch mr-2"></i> 数据结构
                </span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium flex items-center">
                    <i class="fas fa-microchip mr-2"></i> 算法优化
                </span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium flex items-center">
                    <i class="fas fa-database mr-2"></i> 存储系统
                </span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-4 sm:px-6 lg:px-8 py-12">
        <article class="bg-white rounded-xl shadow-lg overflow-hidden">
            <!-- Introduction -->
            <section class="p-8 md:p-12">
                <p class="drop-cap text-lg md:text-xl text-slate-700 leading-relaxed">
                    在计算机科学领域，红黑树和B树是两种至关重要的平衡树数据结构，它们在不同场景下各显神通。本文将从结构特性、时间复杂度、应用场景等多个维度深入比较这两种数据结构，帮助开发者根据实际需求做出明智选择。
                </p>
            </section>

            <!-- Key Differences -->
            <section class="px-8 md:px-12 pb-8">
                <h2 class="text-2xl md:text-3xl font-bold text-slate-800 mb-6 flex items-center">
                    <i class="fas fa-balance-scale-left text-purple-600 mr-3"></i>
                    核心差异对比
                </h2>
                
                <div class="grid md:grid-cols-2 gap-8">
                    <!-- Red-Black Tree -->
                    <div class="feature-card p-6 bg-slate-50 rounded-lg">
                        <div class="flex items-center mb-4">
                            <div class="w-10 h-10 rounded-full bg-red-500 flex items-center justify-center text-white mr-4">
                                <i class="fas fa-tree text-lg"></i>
                            </div>
                            <h3 class="text-xl font-bold text-slate-800">红黑树</h3>
                        </div>
                        <ul class="space-y-3 text-slate-700">
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>二叉平衡搜索树，每个节点最多2个子节点</span>
                            </li>
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>通过颜色标记和旋转操作维持平衡</span>
                            </li>
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>查找、插入、删除均为O(log n)时间复杂度</span>
                            </li>
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>适合内存中的数据组织</span>
                            </li>
                        </ul>
                    </div>
                    
                    <!-- B-Tree -->
                    <div class="feature-card p-6 bg-slate-50 rounded-lg">
                        <div class="flex items-center mb-4">
                            <div class="w-10 h-10 rounded-full bg-blue-500 flex items-center justify-center text-white mr-4">
                                <i class="fas fa-sitemap text-lg"></i>
                            </div>
                            <h3 class="text-xl font-bold text-slate-800">B树</h3>
                        </div>
                        <ul class="space-y-3 text-slate-700">
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>多路平衡搜索树，节点可包含多个子节点</span>
                            </li>
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>通过节点分裂与合并维持平衡</span>
                            </li>
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>查询效率O(log n)，但能显著减少磁盘I/O</span>
                            </li>
                            <li class="flex items-start">
                                <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                                <span>专为磁盘存储系统优化</span>
                            </li>
                        </ul>
                    </div>
                </div>
            </section>

            <!-- Visualization -->
            <section class="px-8 md:px-12 pb-12">
                <h2 class="text-2xl md:text-3xl font-bold text-slate-800 mb-6 flex items-center">
                    <i class="fas fa-project-diagram text-purple-600 mr-3"></i>
                    结构可视化对比
                </h2>
                
                <div class="visualization-container p-6">
                    <div class="mermaid">
                        graph TD
                            subgraph 红黑树
                                A((R)) --> B((B))
                                A --> C((B))
                                B --> D((R))
                                B --> E((R))
                                style A fill:#ef4444,stroke:#000,color:#fff
                                style B fill:#000,stroke:#000,color:#fff
                                style C fill:#000,stroke:#000,color:#fff
                                style D fill:#ef4444,stroke:#000,color:#fff
                                style E fill:#ef4444,stroke:#000,color:#fff
                            end
                            
                            subgraph B树(阶数m=3)
                                F[20, 40] --> G[10, 15]
                                F --> H[25, 30, 35]
                                F --> I[50, 60]
                            end
                    </div>
                </div>
            </section>

            <!-- Application Scenarios -->
            <section class="px-8 md:px-12 pb-8">
                <h2 class="text-2xl md:text-3xl font-bold text-slate-800 mb-6 flex items-center">
                    <i class="fas fa-laptop-code text-purple-600 mr-3"></i>
                    应用场景分析
                </h2>
                
                <div class="grid md:grid-cols-2 gap-8">
                    <div>
                        <h3 class="text-xl font-semibold text-slate-800 mb-4 border-b pb-2">红黑树典型应用</h3>
                        <ul class="space-y-4">
                            <li class="flex items-start">
                                <div class="bg-purple-100 p-2 rounded-full mr-3">
                                    <i class="fas fa-code text-purple-600"></i>
                                </div>
                                <div>
                                    <h4 class="font-medium text-slate-800">高级语言标准库</h4>
                                    <p class="text-slate-600 text-sm">Java的TreeMap/TreeSet，C++的map/set等</p>
                                </div>
                            </li>
                            <li class="flex items-start">
                                <div class="bg-purple-100 p-2 rounded-full mr-3">
                                    <i class="fas fa-memory text-purple-600"></i>
                                </div>
                                <div>
                                    <h4 class="font-medium text-slate-800">内存数据库索引</h4>
                                    <p class="text-slate-600 text-sm">Redis的有序集合(zset)底层实现</p>
                                </div>
                            </li>
                            <li class="flex items-start">
                                <div class="bg-purple-100 p-2 rounded-full mr-3">
                                    <i class="fas fa-network-wired text-purple-600"></i>
                                </div>
                                <div>
                                    <h4 class="font-medium text-slate-800">进程调度</h4>
                                    <p class="text-slate-600 text-sm">Linux内核的完全公平调度器(CFS)</p>
                                </div>
                            </li>
                        </ul>
                    </div>
                    
                    <div>
                        <h3 class="text-xl font-semibold text-slate-800 mb-4 border-b pb-2">B树典型应用</h3>
                        <ul class="space-y-4">
                            <li class="flex items-start">
                                <div class="bg-blue-100 p-2 rounded-full mr-3">
                                    <i class="fas fa-database text-blue-600"></i>
                                </div>
                                <div>
                                    <h4 class="font-medium text-slate-800">关系型数据库</h4>
                                    <p class="text-slate-600 text-sm">MySQL的InnoDB存储引擎索引</p>
                                </div>
                            </li>
                            <li class="flex items-start">
                                <div class="bg-blue-100 p-2 rounded-full mr-3">
                                    <i class="fas fa-hdd text-blue-600"></i>
                                </div>
                                <div>
                                    <h4 class="font-medium text-slate-800">文件系统</h4>
                                    <p class="text-slate-600 text-sm">NTFS、ReiserFS、XFS等文件系统索引</p>
                                </div>
                            </li>
                            <li class="flex items-start">
                                <div class="bg-blue-100 p-2 rounded-full mr-3">
                                    <i class="fas fa-cloud text-blue-600"></i>
                                </div>
                                <div>
                                    <h4 class="font-medium text-slate-800">大规模数据存储</h4>
                                    <p class="text-slate-600 text-sm">MongoDB、CouchDB等NoSQL数据库</p>
                                </div>
                            </li>
                        </ul>
                    </div>
                </div>
            </section>

            <!-- Code Example -->
            <section class="px-8 md:px-12 pb-12">
                <h2 class="text-2xl md:text-3xl font-bold text-slate-800 mb-6 flex items-center">
                    <i class="fas fa-laptop-code text-purple-600 mr-3"></i>
                    代码示例：红黑树插入操作
                </h2>
                
                <div class="code-bg rounded-lg overflow-hidden">
                    <div class="flex items-center px-4 py-2 bg-slate-800 border-b border-slate-700">
                        <div class="flex space-x-2 mr-4">
                            <span class="w-3 h-3 rounded-full bg-red-500"></span>
                            <span class="w-3 h-3 rounded-full bg-yellow-500"></span>
                            <span class="w-3 h-3 rounded-full bg-green-500"></span>
                        </div>
                        <span class="text-slate-400 text-sm">red-black-tree.ts</span>
                    </div>
                    <pre class="p-4 text-slate-100 overflow-x-auto"><code class="language-typescript">class RBNode {
    value: number;
    color: 'red' | 'black';
    left: RBNode | null;
    right: RBNode | null;
    parent: RBNode | null;

    constructor(value: number) {
        this.value = value;
        this.color = 'red'; // 新节点默认为红色
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

function insert(root: RBNode | null, value: number): RBNode {
    // 标准BST插入
    let newNode = new RBNode(value);
    let current = root;
    let parent = null;
    
    while (current !== null) {
        parent = current;
        if (value < current.value) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    
    newNode.parent = parent;
    if (parent === null) {
        root = newNode;
    } else if (value < parent.value) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    
    // 红黑树平衡调整
    return fixInsert(root, newNode);
}

function fixInsert(root: RBNode, node: RBNode): RBNode {
    // 此处省略红黑树平衡调整逻辑
    // 包括颜色翻转和旋转操作
    return root;
}</code></pre>
                </div>
            </section>

            <!-- Performance Comparison -->
            <section class="px-8 md:px-12 pb-12">
                <h2 class="text-2xl md:text-3xl font-bold text-slate-800 mb-6 flex items-center">
                    <i class="fas fa-tachometer-alt text-purple-600 mr-3"></i>
                    性能特征对比
                </h2>
                
                <div class="overflow-x-auto">
                    <table class="w-full border-collapse">
                        <thead>
                            <tr class="bg-slate-100 text-left">
                                <th class="p-3 font-semibold text-slate-700 border-b">指标</th>
                                <th class="p-3 font-semibold text-slate-700 border-b">红黑树</th>
                                <th class="p-3 font-semibold text-slate-700 border-b">B树(阶数m=100)</th>
                            </tr>
                        </thead>
                        <tbody>
                            <tr class="border-b border-slate-200 hover:bg-slate-50">
                                <td class="p-3 font-medium">查找时间复杂度</td>
                                <td class="p-3">O(log n)</td>
                                <td class="p-3">O(log n)</td>
                            </tr>
                            <tr class="border-b border-slate-200 hover:bg-slate-50">
                                <td class="p-3 font-medium">插入时间复杂度</td>
                                <td class="p-3">O(log n)</td>
                                <td class="p-3">O(log n)</td>
                            </tr>
                            <tr class="border-b border-slate-200 hover:bg-slate-50">
                                <td class="p-3 font-medium">删除时间复杂度</td>
                                <td class="p-3">O(log n)</td>
                                <td class="p-3">O(log n)</td>
                            </tr>
                            <tr class="border-b border-slate-200 hover:bg-slate-50">
                                <td class="p-3 font-medium">空间复杂度</td>
                                <td class="p-3">O(n)</td>
                                <td class="p-3">O(n)</td>
                            </tr>
                            <tr class="border-b border-slate-200 hover:bg-slate-50">
                                <td class="p-3 font-medium">平均节点高度</td>
                                <td class="p-3">~1.0 * log₂n</td>
                                <td class="p-3">~0.5 * logₘn</td>
                            </tr>
                            <tr class="border-b border-slate-200 hover:bg-slate-50">
                                <td class="p-3 font-medium">磁盘I/O性能</td>
                                <td class="p-3">较差</td>
                                <td class="p-3 text-green-600 font-medium">优秀</td>
                            </tr>
                        </tbody>
                    </table>
                </div>
            </section>

            <!-- Selection Guide -->
            <section class="px-8 md:px-12 pb-12">
                <h2 class="text-2xl md:text-3xl font-bold text-slate-800 mb-6 flex items-center">
                    <i class="fas fa-question-circle text-purple-600 mr-3"></i>
                    如何选择合适的结构？
                </h2>
                
                <div class="bg-indigo-50 border-l-4 border-indigo-500 p-6 rounded-lg">
                    <h3 class="text-xl font-semibold text-slate-800 mb-3">决策指南</h3>
                    <ul class="space-y-3 text-slate-700">
                        <li class="flex items-start">
                            <i class="fas fa-check text-indigo-600 mt-1 mr-3"></i>
                            <span><strong>选择红黑树</strong>：当数据完全存储在内存中，且需要高效的动态插入/删除操作时（如实现有序映射或集合）。</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check text-indigo-600 mt-1 mr-3"></i>
                            <span><strong>选择B树</strong>：当数据量巨大无法完全装入内存，或需要最小化磁盘I/O时（如数据库索引或文件系统）。</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check text-indigo-600 mt-1 mr-3"></i>
                            <span><strong>考虑B+树</strong>：如果需要范围查询（B树的变种，常用于数据库系统，叶子节点形成链表）。</span>
                        </li>
                    </ul>
                </div>
            </section>
        </article>
    </main>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: false,
                htmlLabels: true
            }
        });
    </script>
</body>
</html>